#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10,INF=0x3f3f3f3f;
int n,m,st[MAXN],ed[MAXN];
multiset<int>a,b;
priority_queue<int,vector<int>,greater<int> >q;
map<int,int>mp;
void insert(int x)
{
	if(!mp[x]++)a.insert(x);
}
void del(int x)
{
	if(!--mp[x])a.erase(x);
}
void push(int x)
{
	int l=*--b.lower_bound(x),r=*b.lower_bound(x);
	q.push(min(x-l,r-x));
	b.insert(x);
}
int main()
{
	scanf("%d%d",&n,&m);
	b.insert(INF);
	b.insert(-INF);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&st[i]);
		ed[i]=st[i];
		push(st[i]);
	}
	for(int i=1;i<n;++i)insert(abs(ed[i]-st[i+1]));
	char temp[20];
	for(int i=1;i<=m;++i)
	{
		scanf("%s",temp+1);
		if(temp[1]=='I')
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(x!=n)del(abs(ed[x]-st[x+1]));
			insert(abs(ed[x]-y));
			insert(abs(y-st[x+1]));
			ed[x]=y;
			push(y);
		}
		else if(temp[5]=='S')printf("%d\n",q.top());
		else printf("%d\n",*a.begin());
	}
	return 0;
}
